package 剑指offer;

public class n个骰子的点数 {

//    确定问题解的表达式。可将f(n, s) 表示n个骰子点数的和为s的排列情况总数
//    确定状态转移方程。n个骰子点数和为s的种类数只与n-1个骰子的和有关。
//    因为一个骰子有六个点数，那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话，
//    f(n,s)=f(n-1,s-1)，当第n个骰子点数为2的话，f(n,s)=f(n-1,s-2)，…，依次类推。
//    在n-1个骰子的基础上，再增加一个骰子出现点数和为s的结果只有这6种情况！
//    那么有：f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)
//    上面就是状态转移方程，已知初始阶段的解为：当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

    public double[] dicesProbability(int n) {
        int[][] dp = new int[n + 1][6 * n + 1];
        double[] doubles = new double[5 * n + 1];
        double all= Math.pow(6,n);
        //初始化条件
        for (int i = 1; i <=6 ; i++) {
            dp[1][i]=1;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = i; j <=6*n ; j++) {
                for (int k = 1; k <=6 ; k++) {
                    dp[i][j] += j>k?dp[i-1][j-k]:0;
                    if (i==n)
                        doubles[j-i]=dp[i][j]/all;
                }
            }
        }
        return doubles;
    }
}
